// using System.Collections.Generic;
// using UnityEngine;


// namespace JPS {
// 	internal struct JPSNode{
// 		public JPSNode(int x, int y) : this(new Vector2Int(x, y)) { }
// 		public JPSNode(Vector2Int l) {
// 			Location = l;
// 		}
// 		public Vector2Int Location { get; private set; }

// 		public float Cost { get; set; }
// 		public JPSNode Parent { get; set; }
// 		public bool Opened { get; set; }
// 		public bool Closed { get; set; }
// 		public bool Forced { get; set; }

// 		public void Revert() {
// 			Cost = 0;
// 			Parent = null;
// 			Closed = false;
// 			Opened = false;
// 			Forced = false;
// 		}
// 	}

// 	public class JPSPath : PathFinder {
// 		private readonly JPSGrid _grid;
// 		private Vector2Int _start = JPSUtils.NullVec, _goal = JPSUtils.NullVec;
// 		private readonly FastPriorityQueue<JPSNode> _open;

// 		public JPSPath(JPSGrid grid, int cap = 256) {
// 			_grid = grid;
// 			_open = new FastPriorityQueue<JPSNode>(cap);
// 		}

// 		public override List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal) {
// 			if (!_grid._N(start.x, start.y) || !_grid._N(goal.x, goal.y))
// 				return null;
// 			_grid.Clear();
// 			_start = start;
// 			_goal = goal;
// 			_open.Clear();
// 			var startNode = new JPSNode(_start) { Cost = 0, Opened = true, Closed = false };
// 			_open.Enqueue(startNode, startNode.Cost);
// 			while (_open.Count != 0) {
// 				JPSNode current = _open.Dequeue();
// 				current.Closed = true;
// 				if (current.Location == goal)
// 					return Trace(current);
// 				IdentitySuccessors(current);
// 			}
// 			return null;
// 		}

// 		/// <summary>
// 		/// 搜索后继的跳点
// 		/// </summary>
// 		/// <param name="node"></param>
// 		private void IdentitySuccessors(JPSNode node) {
// 			// 直接开始向对应方向搜索跳点，因为剪枝已经在搜索邻居时完成了
// 			foreach (JPSNode neighbor in _grid.Neighbours(node)) {
// 				Vector2Int jumpPoint = Jump(node.Location, neighbor.Location - node.Location, 1);
// 				if (jumpPoint == JPSUtils.NullVec) continue;
// 				// 在这个方向上找到跳点的话
// 				JPSNode jumpNode = _grid[jumpPoint];
// 				if (jumpNode.Closed)
// 					continue;
// 				// 计算移动到跳点的代价
// 				float moveCost = Distance(jumpPoint - node.Location);
// 				float newCost = node.Cost + moveCost;
// 				// 检查是否在openset中
// 				if (!jumpNode.Opened) {
// 					// 加入
// 					jumpNode.Opened = true;
// 					jumpNode.Parent = node;
// 					jumpNode.Cost = newCost;
// 					_open.Enqueue(jumpNode, jumpNode.Cost);
// 				}
// 				// 比较代价确认是否更新
// 				else if (newCost < jumpNode.Cost) {
// 					jumpNode.Parent = node;
// 					jumpNode.Cost = newCost;
// 					_open.UpdatePriority(jumpNode, newCost);
// 				}
// 			}
// 		}

// 		private float Distance(Vector2Int delta) {
// 			return delta.magnitude;
// 		}

// 		private Vector2Int Jump(Vector2Int node, Vector2Int dir, int k) {
// 			Vector2Int next = node + dir * new Vector2Int(k, k);
// 			// 如果下一个节点无法通行，就不是跳点
// 			if (!_grid._N(next.x, next.y))
// 				return JPSUtils.NullVec;
// 			// 如果到达终点，终点也是跳点
// 			if (next == _goal)
// 				return next;
// 			// 确定是否存在强制节点
// 			_grid[next].Parent = _grid[node];
// 			foreach (var n in _grid.Neighbours(_grid[next]))
// 				if (n.Forced)
// 					return next;
// 			// 确定对角线的轴向分量上的跳点
// 			if (dir.x != 0 && dir.y != 0) {
// 				if (Jump(next, new Vector2Int(0, dir.y), 1) != JPSUtils.NullVec)
// 					return next;
// 				if (Jump(next, new Vector2Int(dir.x, 0), 1) != JPSUtils.NullVec)
// 					return next;
// 				if (_grid._N(next.x, next.y + dir.y) && _grid._N(next.x + dir.x, next.y))
// 					return Jump(node, dir, k + 1);
// 				return JPSUtils.NullVec;
// 			}
// 			// 继续看下一个
// 			return Jump(node, dir, k + 1);
// 		}

// 		/// <summary>
// 		/// 回溯生成路径
// 		/// </summary>
// 		/// <param name="node"></param>
// 		/// <returns></returns>
// 		private List<Vector2Int> Trace(JPSNode node) {
// 			var path = new List<Vector2Int> { node.Location };
// 			while (node.Parent != null) {
// 				node = node.Parent;
// 				path.Add(node.Location);
// 			}
// 			path.Reverse();
// 			return path;
// 		}
// 	}

// 	public class JPSGrid {
// 		// 边界设定
// 		private readonly int _boundsMaxX;
// 		private readonly int _boundsMaxY;
// 		private readonly int _boundsMinX;
// 		private readonly int _boundsMinY;

// 		// 实际内容
// 		private readonly bool[,] _navigable;
// 		private readonly JPSNode[,] _grid;

// 		public JPSGrid(bool[,] navigable) {
// 			_boundsMinX = 0;
// 			_boundsMaxX = navigable.GetUpperBound(0);
// 			_boundsMinY = 0;
// 			_boundsMaxY = navigable.GetUpperBound(1);
// 			_navigable = navigable;

// 			_grid = new JPSNode[_boundsMaxX + 1, _boundsMaxY + 1];
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++)
// 					_grid[x, y] = new JPSNode(x, y);
// 		}

// 		public void Clear() {
// 			if (_grid != null)
// 				foreach (var g in _grid)
// 					g.Revert();
// 		}

// 		internal JPSNode this[int x, int y] { get { return _grid[x, y]; } }
// 		internal JPSNode this[Vector2Int location] { get { return _grid[location.x, location.y]; } }

// 		// 判断是否可以访问
// 		public bool _N(int x, int y) {
// 			return InBounds(x, y) && _navigable[x, y];
// 		}

// 		public bool InBounds(int x, int y) {
// 			return x >= _boundsMinX && x <= _boundsMaxX &&
// 				   y >= _boundsMinY && y <= _boundsMaxY;
// 		}

// 		internal IEnumerable<JPSNode> Neighbours(JPSNode node) {
// 			if (node.Parent != null) {
// 				// 有父亲节点，需要剪枝
// 				Vector2Int n = node.Location;
// 				Vector2Int p = node.Parent.Location;
// 				Vector2Int d = n - p;
// 				d.x /= Mathf.Max(Mathf.Abs(d.x), 1);
// 				d.y /= Mathf.Max(Mathf.Abs(d.y), 1);
// 				// 对角线
// 				if (d.x != 0 && d.y != 0) {
// 					// 轴向分量
// 					if (_N(n.x, n.y + d.y))
// 						yield return this[n.x, n.y + d.y];
// 					if (_N(n.x + d.x, n.y))
// 						yield return this[n.x + d.x, n.y];
// 					// 往前看
// 					if (_N(n.x, n.y + d.y) && _N(n.x + d.x, n.y) && _N(n.x + d.x, n.y + d.y))
// 						yield return this[n.x + d.x, n.y + d.y];
// 				}
// 				// 垂直轴向
// 				else if (d.x == 0) {
// 					// 向前看
// 					if (_N(n.x, n.y + d.y))
// 						yield return this[n.x, n.y + d.y];
// 					// 向左看
// 					if (!_N(n.x - 1, n.y - d.y) && _N(n.x - 1, n.y)) {
// 						this[n.x - 1, n.y].Forced = true;
// 						yield return this[n.x - 1, n.y];
// 						if (_N(n.x - 1, n.y + d.y))
// 							yield return this[n.x - 1, n.y + d.y];
// 					}
// 					// 向右看
// 					if (!_N(n.x + 1, n.y - d.y) && _N(n.x + 1, n.y)) {
// 						this[n.x + 1, n.y].Forced = true;
// 						yield return this[n.x + 1, n.y];
// 						if (_N(n.x + 1, n.y + d.y))
// 							yield return this[n.x + 1, n.y + d.y];
// 					}
// 				}
// 				// 水平轴向
// 				else if (d.y == 0) {
// 					if (_N(n.x + d.x, n.y))
// 						yield return this[n.x + d.x, n.y];
// 					// 向左看
// 					if (!_N(n.x - d.x, n.y + 1) && _N(n.x, n.y + 1)) {
// 						this[n.x, n.y + 1].Forced = true;
// 						yield return this[n.x, n.y + 1];
// 						if (_N(n.x + d.x, n.y + 1))
// 							yield return this[n.x + d.x, n.y + 1];
// 					}
// 					// 向右看
// 					if (!_N(n.x - d.x, n.y - 1) && _N(n.x, n.y - 1)) {
// 						this[n.x, n.y - 1].Forced = true;
// 						yield return this[n.x, n.y - 1];
// 						if (_N(n.x + d.x, n.y - 1))
// 							yield return this[n.x + d.x, n.y - 1];
// 					}
// 				}
// 			} else {
// 				// 是起点
// 				bool[] bs = new bool[8];
// 				for (var i = 0; i < 8; i++)
// 					bs[i] = _N(node.Location.x + JPSUtils.DirToVec[i].x, node.Location.y + JPSUtils.DirToVec[i].y);
// 				for (int i = 0; i < 3; i++)
// 					if (bs[i])
// 						yield return this[node.Location + JPSUtils.DirToVec[i]];
// 				if (bs[(int)JPSDir.N] && bs[(int)JPSDir.E] && bs[(int)JPSDir.NE])
// 					yield return this[node.Location + JPSUtils.DirToVec[(int)JPSDir.NE]];
// 				if (bs[(int)JPSDir.S] && bs[(int)JPSDir.E] && bs[(int)JPSDir.SE])
// 					yield return this[node.Location + JPSUtils.DirToVec[(int)JPSDir.SE]];
// 				if (bs[(int)JPSDir.N] && bs[(int)JPSDir.W] && bs[(int)JPSDir.NW])
// 					yield return this[node.Location + JPSUtils.DirToVec[(int)JPSDir.NW]];
// 				if (bs[(int)JPSDir.S] && bs[(int)JPSDir.W] && bs[(int)JPSDir.SW])
// 					yield return this[node.Location + JPSUtils.DirToVec[(int)JPSDir.SW]];
// 			}
// 		}
// 	}
// }